Efficient algorithms for training the parameters of hidden Markov models using stochastic expectation maximization EM training and Viterbi training

摘要

Background: Hidden Markov models are widely employed by numerousbioinformatics programs used today. Applications range widely from comparativegene prediction to time-series analyses of micro-array data. The parameters ofthe underlying models need to be adjusted for specific data sets, for examplethe genome of a particular species, in order to maximize the predictionaccuracy. Computationally efficient algorithms for parameter training are thuskey to maximizing the usability of a wide range of bioinformatics applications. Results: We introduce two computationally efficient training algorithms, onefor Viterbi training and one for stochastic expectation maximization (EM)training, which render the memory requirements independent of the sequencelength. Unlike the existing algorithms for Viterbi and stochastic EM trainingwhich require a two-step procedure, our two new algorithms require only onestep and scan the input sequence in only one direction. We also implement thesetwo new algorithms and the already published linear-memory algorithm for EMtraining into the hidden Markov model compiler HMM-Converter and examine theirrespective practical merits for three small example models. Conclusions: Bioinformatics applications employing hidden Markov models canuse the two algorithms in order to make Viterbi training and stochastic EMtraining more computationally efficient. Using these algorithms, parametertraining can thus be attempted for more complex models and longer trainingsequences. The two new algorithms have the added advantage of being easier toimplement than the corresponding default algorithms for Viterbi training andstochastic EM training.